The present invention relates generally to enhancing instruction level parallelism in a multi-issue processor environment, and relates more particularly to a technique for the efficient recovery of exceptions generated during speculative execution.
The performance of modern microprocessors has been increasing at a rapid and dramatic pace. Although microprocessor clock speeds keep increasing at a relatively moderate pace, microprocessor processing power has been increasing dramatically due to microprocessors having parallel architecture features. In 1990, conventional microprocessors executed one instruction per cycle. By 1995, conventional microprocessors had the ability to execute up to four instructions per cycle. It is anticipated that within about the next year, microprocessors will be widely available that are capable of executing up to at least eight instructions per cycle. A microprocessor that is capable of executing multiple instructions per cycle is also referred to as a multi-issue processor.
Despite the dramatic increase in the potential processing power of multi-issue processors, deficiencies in compiler technology and supporting architecture design typically limit the actual processing power realized to only a small fraction of the massive potential of the multi-issue processor. Unless a compiler and the supporting hardware expose substantial portions of the instructions in parallel to the microprocessor hardware, the processing power potential of the microprocessor is largely wasted. Thus, much attention has been focused upon techniques to increase the amount of instruction level parallelism (ILP) visible to the multi-issue microprocessor so as to realize the great processing power advantages of multi-issue microprocessors.
Three techniques have been studied individually to increase ILP: (1) control speculation, (2) data speculation, and (3) predication. Control speculation and data speculation fall into a more general category of speculative execution, where the execution of instructions are performed before their proper execution conditions have been determined.
Control speculation breaks control dependencies which occur between branches and other operations. In other words, instead of conventionally executing instructions sequentially, the schedule of instructions is modified such that certain instructions are moved up in the schedule and executed in parallel with other instructions and at a time when it is not necessarily known with certainty that the control flow of the code will require actual execution of those instructions. Such instructions are executed speculatively, i.e., executed based upon an assumption that the control flow will dictate that they should actually be executed.
An operation is control dependent on a branch if the branch determines whether control flow will actually reach the operation during the execution of the program. A control dependence is broken by guessing a branch will go in a particular direction, thereby making operations along the predicted direction to execute independently of the branch. Breaking control dependencies through control speculation reduces control dependence height and results in a more compact instruction execution schedule.
FIG. 6 illustrates a very simple example depicting control speculation. On the left is illustrated the instruction schedule for a sample instruction segment that dies not use control speculation. On the right is illustrated the same set of instructions, but scheduled using control speculation with a two-issue processor, sequence of execution of each of the processors being indicated by the two separate columns. When control speculation, is used the instructions associated with the LABEL1 may be moved up in the schedule and executed control speculatively (indicated with  less than CS greater than ) simultaneously with other instructions, as illustrated. As can be seen in the speculative version, two different LD instructions and two different ADD instructions are executed simultaneously. At the location where the LD r1, ADDR2 instruction was located (at LABEL1) in the non-speculative version, there is substituted a CHK instruction in the speculative version that checks register R1 to determine if an exception occurred as a result of the control speculative execution. If no exception was detected from register R1, then the speculation was successful and, as seen, the length of the code schedule has been reduced. However, if an exception was detected from register R1, such as if the memory being accessed by the load caused a segmentation violation, page fault, TLB (Translation Lookaside Buffer) miss, or cache memory miss, then the load of the control speculation redoes additional handling, and recovery should be initiated by re-executing the speculatively executed set of instructions.
Data speculation breaks data flow dependencies between memory operations. Two memory operations are flow dependent on one another if the first operation writes a value to an address and the second operation potentially reads from the same address. Thus, the original order of the memory operations must be maintained to ensure proper value flow. For a dependence to exist, the operation need only potentially read from the same address. If two memory operations are not provably independent, they are dependent by definition. A memory dependence where the dependence control is not certain is referred to as an ambiguous memory dependence. A memory dependence is broken by guessing that the two memory operations will access different locations, thereby making the operations independent of one another. With data speculation, memory operations may be aggressively reordered to effectively reduce memory dependence height which further results in a more compact instruction schedule.
Another technique that has been explored to increase ILP is predication. Predicated execution is a mechanism that supports conditional execution of individual operations based on Boolean guards, which are implemented as predicate register values. With predication, the representation of programmatic control flow can be inherently changed thereby physically restructing the control flow into a more efficient form execution on a wide-issue processor.
Speculative execution, however, introduces additional complexities and requires different and more sophisticated handling of particular conditions. One of the greatest challenges in dealing with speculatively executed instructions is how to handle exception or error conditions to ensure proper program control. When a non-speculatively executed instruction generates an exception condition, the exception is reported and handled immediately. However, when a speculatively executed instructions encounters an exception condition, it may be necessary to defer the exception to ensure that it does not interfere with proper operation of the program. Furthermore, exception recovery may require a long and time-consuming process, so it is frequently preferable to defer an exception encountered in a speculatively executed instruction until it is determined with certainty that the program flow actually requires execution of the instruction.
U.S. Pat. No. 5,692,169 to Kathail et al. for a Method and System for Deferring Exceptions Generated During Speculative Execution is directed to a technique where exceptions generated during execution of speculative instructions are deferred. The reference indicates that deferred exceptions may be detected and reported using a check operation either incorporated into a non-speculative operation or inserted as a separate check operation. The reference, however, does not provide a particular technique for recovery, but merely states that xe2x80x9cwhen an exception is detected, the CPU branches to an exception handling routine.xe2x80x9d
Smith et al. in Efficient Superscalar Performance Through Boosting, Proceedings of the Fifth International Conference on Architecture Support for Programming Languages and Operating Systems, October, 1992, pp. 248-259, propose a model that where the compiler generates recovery blocksxe2x80x94the exact sequence of instructions that must be re-executed when an exception is detected by a particular excepting speculated instruction. U.S. Pat. No. 5,694,577 to Kiyohara et al. for a Memory Conflict Buffer for Achieving Memory Disambiguation in Compile-Time Code Schedule also teaches using recovery blocks to handle exceptions from speculatively executed instructions. In addition, Kiyohara discloses a memory conflict buffer that may be used to detect a situation where data speculation recovery is needed as a result of data pre-loaded from a memory location which is affected by one or more subsequent store operations.
Although the use of recovery blocks may reduce complexity in the exception handling state, it results in a dramatic increase in code size due to the addition of the recovery blocks. An additional disadvantage of recovery blocks is that the code is typically organized such that the blocks are located at a section of the code which is relatively distant from the code that generated the exception, resulting in frequent and time-consuming page faults, translation look-aside buffer misses, or long latency cache misses.
The foregoing limitations and disadvantages of the prior art are addressed in the present invention which provides a technique for handling recovery from speculatively executed instructions which does not use separate recovery blocks. This technique of the present invention promotes better instruction cache performance by the selective re-use of code for recovery instead of using recovery blocks. In addition, the elimination of recovery blocks results in significantly smaller code size than for an implementation that requires additional explicit recovery code. In addition, the present invention provides an architecture and method for efficient exception handling when combining control speculation, data speculation and predication, thereby resulting in substantially enhanced ILP.
The advantages of the present invention are realized in a preferred embodiment that provides an instruction set capable of distinguishing between speculative and non-speculative instructions, a mechanism for deferring exceptions on speculatively executed instructions, a mechanism to detect and handle memory conflicts arising from speculatively executed instructions, and an architecture that ensures selective execution of only data flow successors of excepting speculative instructions during recovery. The exception recovery technique of the present invention is particularly advantageous, and may be implemented by providing a bit to each register that serves as a flag or tag to indicate which instructions should be executed during recovery. Thus, by providing one or two additional bits in operation encodings, two bits added to each register, and a memory conflict buffer, the present invention can accurately detect, report, and recover from exactly those exceptions that would have occurred in non-speculated code, and can recover from memory conflicts in data-speculative code.